SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Sequential pattern mining</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Sequential pattern mining</span></span>

</h1>

</header>

<p><b>Sequential pattern mining</b> is a topic of <a href="Data_mining" title="Data mining">data mining</a> concerned with finding statistically relevant patterns between data examples where the values are delivered in a sequence.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It is usually presumed that the values are discrete, and thus <a href="Time_series" title="Time series">time series</a> mining is closely related, but usually considered a different activity. Sequential pattern mining is a special case of <a href="Structured_data_mining" class="mw-redirect" title="Structured data mining">structured data mining</a>.

</p><p>There are several key traditional computational problems addressed within this field. These include building efficient databases and indexes for sequence information, extracting the frequently occurring patterns, comparing sequences for <a href="Similarity_measure" title="Similarity measure">similarity</a>, and recovering missing sequence members. In general, sequence mining problems can be classified as <i>string mining</i> which is typically based on <a href="String_(computer_science)" title="String (computer science)">string processing algorithms</a> and <i>itemset mining</i> which is typically based on <a href="Association_rule_learning" title="Association rule learning">association rule learning</a>. <i>Local process models</i> <sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> extend sequential pattern mining to more complex patterns that can include (exclusive) choices, loops, and concurrency constructs in addition to the sequential ordering construct.

</p>

<div class="mw-heading mw-heading2"><h2 id="String_mining">String mining</h2></div>

<p>String mining typically deals with a limited <a href="Alphabet" title="Alphabet">alphabet</a> for items that appear in a <a href="Sequence" title="Sequence">sequence</a>, but the sequence itself may be typically very long. Examples of an alphabet can be those in the <a href="ASCII" title="ASCII">ASCII</a> character set used in natural language text, <a href="Nucleotide" title="Nucleotide">nucleotide</a> bases 'A', 'G', 'C' and 'T' in <a href="DNA_sequences" class="mw-redirect" title="DNA sequences">DNA sequences</a>, or <a href="Amino_acids" class="mw-redirect" title="Amino acids">amino acids</a> for <a href="Protein_sequences" class="mw-redirect" title="Protein sequences">protein sequences</a>. In <a href="Biology" title="Biology">biology</a> applications analysis of the arrangement of the alphabet in strings can be used to examine <a href="Gene" title="Gene">gene</a> and <a href="Protein" title="Protein">protein</a> sequences to determine their properties. Knowing the sequence of letters of a <a href="DNA" title="DNA">DNA</a> or a <a href="Protein" title="Protein">protein</a> is not an ultimate goal in itself. Rather, the major task is to understand the sequence, in terms of its structure and <a href="Function_(biology)" title="Function (biology)">biological function</a>. This is typically achieved first by identifying individual regions or structural units within each sequence and then assigning a function to each structural unit. In many cases this requires comparing a given sequence with previously studied ones. The comparison between the strings becomes complicated when <a href="Insertion_(genetics)" title="Insertion (genetics)">insertions</a>, <a href="Deletion_(genetics)" title="Deletion (genetics)">deletions</a> and <a href="Mutations" class="mw-redirect" title="Mutations">mutations</a> occur in a string.

</p><p>A survey and taxonomy of the key algorithms for sequence comparison for bioinformatics is presented by Abouelhoda & Ghanem (2010), which include:<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><b>Repeat-related problems:</b> that deal with operations on single sequences and can be based on <a href="String_searching_algorithm" class="mw-redirect" title="String searching algorithm">exact string matching</a> or <a href="Approximate_string_matching" title="Approximate string matching">approximate string matching</a> methods for finding dispersed fixed length and maximal length repeats, finding tandem repeats, and finding unique subsequences and missing (un-spelled) subsequences.</li>

<li><b>Alignment problems:</b> that deal with comparison between strings by first aligning one or more sequences; examples of popular methods include <a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a> for comparing a single sequence with multiple sequences in a database, and <a href="ClustalW" class="mw-redirect" title="ClustalW">ClustalW</a> for multiple alignments. Alignment algorithms can be based on either exact or approximate methods, and can also be classified as global alignments, semi-global alignments and local alignment. See <a href="Sequence_alignment" title="Sequence alignment">sequence alignment</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Itemset_mining">Itemset mining</h2></div>

<p>Some problems in sequence mining lend themselves to discovering frequent itemsets and the order they appear, for example, one is seeking rules of the form "if a {customer buys a car}, he or she is likely to {buy insurance} within 1 week", or in the context of stock prices, "if {Nokia up and Ericsson up}, it is likely that {Motorola up and Samsung up} within 2 days". Traditionally, itemset mining is used in marketing applications for discovering regularities between frequently co-occurring items in large transactions. For example, by analysing transactions of customer shopping baskets in a supermarket, one can produce a rule which reads "if a customer buys onions and potatoes together, he or she is likely to also buy hamburger meat in the same transaction".

</p><p>A survey and taxonomy of the key algorithms for item set mining is presented by Han et al. (2007).<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>The two common techniques that are applied to sequence databases for <a href="Association_rule_learning" title="Association rule learning">frequent itemset</a> mining are the influential <a href="Apriori_algorithm" title="Apriori algorithm">apriori algorithm</a> and the more-recent <a href="Association_rule_learning#FP-growth_algorithm" title="Association rule learning">FP-growth</a> technique.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>With a great variation of products and user buying behaviors, shelf on which products are being displayed is one of the most important resources in retail environment. Retailers can not only increase their profit but, also decrease cost by proper management of shelf space allocation and products display. To solve this problem, George and Binu (2013) have proposed an approach to mine user <a href="Buying_pattern" class="mw-redirect" title="Buying pattern">buying patterns</a> using PrefixSpan algorithm and place the products on shelves based on the order of mined purchasing patterns.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>Commonly used algorithms include:

</p>

<ul><li><a href="GSP_algorithm" title="GSP algorithm">GSP algorithm</a></li>

<li>Sequential Pattern Discovery using Equivalence classes (SPADE)</li>

<li>FreeSpan</li>

<li>PrefixSpan</li>

<li>MAPres<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup></li>

<li>Seq2Pat (for constraint-based sequential pattern mining)<sup id="cite_ref-hosseininasab2019_8-0" class="reference"><a href="#cite_note-hosseininasab2019-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li></ul>

<ul><li><a href="Collocation_extraction" title="Collocation extraction">Collocation extraction</a> – Computational technique to find word sequences</li>

<li><a href="Process_mining" title="Process mining">Process mining</a> – Data mining technique using event logs</li>

<li><a href="Sequence_analysis" title="Sequence analysis">Sequence analysis</a> – Identification and study of genomic sequences</li>

<li><a href="Sequence_analysis_in_social_sciences" title="Sequence analysis in social sciences">Sequence analysis in social sciences</a> – Analysis of sets of categorical sequences</li>

<li><a href="Sequence_clustering" title="Sequence clustering">Sequence clustering</a></li>

<li><a href="Sequence_labeling" title="Sequence labeling">Sequence labeling</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-columns-2">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMabroukehEzeife2010" class="citation journal cs1">Mabroukeh, N. R.; Ezeife, C. I. (2010). "A taxonomy of sequential pattern mining algorithms". <i>ACM Computing Surveys</i>. <b>43</b>: <span class="nowrap">1–</span>41. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.332.4745">10.1.1.332.4745</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1824795.1824798">10.1145/1824795.1824798</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207180619">207180619</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFBechiniBondielliDell'OglioMarcellonii2023" class="citation journal cs1">Bechini, A.; Bondielli, A.; Dell'Oglio, P.; Marcellonii, F. (2023). <a rel="nofollow" class="external text" href="https://www.aimspress.com/article/id/63e21839ba35de2c6e2b0152">"From basic approaches to novel challenges and applications in Sequential Pattern Mining"</a>. <i>Applied Computing and Intelligence</i>. <b>3</b> (1): <span class="nowrap">44–</span>78. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.3934%2Faci.2023004">10.3934/aci.2023004</a></span>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/11568%2F1172332">11568/1172332</a></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFTaxSidorovaHaakmavan_der_Aalst2016" class="citation journal cs1">Tax, N.; Sidorova, N.; Haakma, R.; van der Aalst, Wil M. P. (2016). "Mining Local Process Models". <i>Journal of Innovation in Digital Ecosystems</i>. <b>3</b> (2): <span class="nowrap">183–</span>196. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1606.06066">1606.06066</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jides.2016.11.001">10.1016/j.jides.2016.11.001</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10872379">10872379</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbouelhodaGhanem2010" class="citation book cs1">Abouelhoda, M.; Ghanem, M. (2010). "String Mining in Bioinformatics". In Gaber, M. M. (ed.). <i>Scientific Data Mining and Knowledge Discovery</i>. Springer. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-02788-8_9">10.1007/978-3-642-02788-8_9</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-02787-1</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFHanChengXinYan2007" class="citation journal cs1">Han, J.; Cheng, H.; Xin, D.; Yan, X. (2007). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10618-006-0059-1">"Frequent pattern mining: current status and future directions"</a>. <i>Data Mining and Knowledge Discovery</i>. <b>15</b> (1): <span class="nowrap">55–</span>86. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10618-006-0059-1">10.1007/s10618-006-0059-1</a></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFGeorgeBinu2013" class="citation journal cs1">George, A.; Binu, D. (2013). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jksuci.2012.07.001">"An Approach to Products Placement in Supermarkets Using PrefixSpan Algorithm"</a>. <i>Journal of King Saud University-Computer and Information Sciences</i>. <b>25</b> (1): <span class="nowrap">77–</span>87. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jksuci.2012.07.001">10.1016/j.jksuci.2012.07.001</a></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFAhmadQazi,_Wajahat_M.Khurshid,_AhmedAhmad,_Munir2008" class="citation journal cs1">Ahmad, Ishtiaq; Qazi, Wajahat M.; Khurshid, Ahmed; Ahmad, Munir; Hoessli, Daniel C.; Khawaja, Iffat; Choudhary, M. Iqbal; Shakoori, Abdul R.; Nasir-ud-Din (1 May 2008). "MAPRes: Mining association patterns among preferred amino acid residues in the vicinity of amino acids targeted for post-translational modifications". <i>Proteomics</i>. <b>8</b> (10): <span class="nowrap">1954–</span>1958. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fpmic.200700657">10.1002/pmic.200700657</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/18491291">18491291</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:22362167">22362167</a>.</cite></span>

</li>

<li id="cite_note-hosseininasab2019-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-hosseininasab2019_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFHosseininasabvan_HoeveCire2019" class="citation journal cs1">Hosseininasab A, van Hoeve WJ, Cire AA (2019). <a rel="nofollow" class="external text" href="https://www.aaai.org/ojs/index.php/AAAI/article/view/3962">"Constraint-Based Sequential Pattern Mining with Decision Diagrams"</a>. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. <b>33</b>: <span class="nowrap">1495–</span>1502. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1811.06086">1811.06086</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1609%2Faaai.v33i01.33011495">10.1609/aaai.v33i01.33011495</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:53427299">53427299</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/fidelity/seq2pat">"Seq2Pat: Sequence-to-Pattern Generation Library"</a>. <i><a href="GitHub" title="GitHub">GitHub</a></i>. 9 April 2022.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.philippe-fournier-viger.com/spmf/">SPMF</a> includes open-source implementations of GSP, PrefixSpan, SPADE, SPAM and many others.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Strings176" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Strings176" style="font-size:114%;margin:0 4em"><a href="String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li>

<li><a href="Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li>

<li><a href="Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li>

<li><a href="Edit_distance" title="Edit distance">Edit distance</a></li>

<li><a href="Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li>

<li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a></li>

<li><a href="Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li>

<li><a href="Lee_distance" title="Lee distance">Lee distance</a></li>

<li><a href="Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li>

<li><a href="Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li>

<li><a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li>

<li><a href="Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li>

<li><a href="Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li>

<li><a href="Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li>

<li><a href="Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li>

<li><a href="Trigram_search" title="Trigram search">Trigram search</a></li>

<li><a href="Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li>

<li><a href="Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li>

<li><a href="Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular grammar</a></li>

<li><a href="Thompson's_construction" title="Thompson's construction">Thompson's construction</a></li>

<li><a href="Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li>

<li><a href="Hirschberg's_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li>

<li><a href="Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li>

<li><a href="Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li>

<li><a href="Substring_index" title="Substring index">Substring index</a>

<ul><li><a href="Suffix_array" title="Suffix array">Suffix array</a></li>

<li><a href="Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix tree</a></li>

<li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>

<li><a href="LCP_array" title="LCP array">LCP array</a></li>

<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>

<li><a href="Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parsing" title="Parsing">Parsing</a></li>

<li><a href="Pattern_matching" title="Pattern matching">Pattern matching</a></li>

<li><a href="Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li>

<li><a href="Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li>

<li><a href="Longest_common_substring" title="Longest common substring">Longest common substring</a></li>

<li>Sorting</li>

<li><a href="Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li>

<li><a href="String_operations" title="String operations">String operations</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-10" href="https://en.wikipedia.org/wiki/?title=Sequential_pattern_mining&oldid=1294948729">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>